/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hojadetrabajo5dos;
import java.util.Vector;
import java.lang.Comparable; 
/**
 *
 * @author RAUL
 */
public class VectorHeap<E extends Comparable<E>> implements PriorityQueue<E> {

    protected Vector<E> data ;
     private int tamano;
    public VectorHeap(){
        data= new Vector<E>(); 
    }
    @Override
    public E getFirst() {
        E datos =this.data.get(0);
        return datos; 
    }

    

    @Override
    public void add(E value) {
        data.add(value);
        percolateUp(data.size()-1);
    }

    @Override
    public boolean isEmpty() {
        if (tamano==0){
            return true;
        } 
        else{
            return false;
        }
    }
    @Override
    public int size() {
        tamano = data.size();
        return tamano;
    }

    @Override
    public void clear() {
        
    }

   
  protected static int parent(int i){
      return (i-1)/2 ;
  }
  protected static int left (int i){
      return 2*i+1; 
  }
  protected static int right (int i){
      return 2*(i+1);
  }

    private void percolateUp(int leaf) {
        int padre = parent(leaf);
        E valor = data.get(leaf);
        while (leaf > 0 &&(valor.compareTo(data.get(padre)) <0)){
            data.set(leaf,data.get(padre));
            leaf = padre;
            padre = parent(leaf);
        } 
        data.set(padre, valor);
  
    }
    @Override
    public E remove(){
        E minVal = getFirst();
        data.set(0,data.get(data.size()-1));
        data.setSize(data.size()-1);
        if(data.size()>1)
            pushDownRoot(0);
               return minVal; 
    }
    
    protected void pushDownRoot(int root){
        int heapSize = data.size();
        E value = data.get(root);
        while (root < heapSize) {
            int numeropos = left(root);
                if (numeropos < heapSize){
                    if ((right(root) < heapSize) && ((data.get(numeropos+1)).compareTo(data.get(numeropos)) < 0))
                        {
                             numeropos++;
                            }
        
                         if ((data.get(numeropos)).compareTo(value) < 0) {
                            data.set(root,data.get(numeropos));
                            root = numeropos; 
                                 } else { 
                                    data.set(root,value);
                                    return; }
                                         } else { 
                                             data.set(root,value);
                                             return;
                                            }
                                }
        }
        
    
    public VectorHeap(Vector<E> v){
        int e;
        data = new Vector<E>(v.size());
        for (e = 0; e < v.size(); e++)
        {   // add elements to heap
            add(v.get(e));
        }
    }
}